package algorithms.tree;

import static algorithms.Util.*;

import java.util.ArrayList;
import java.util.List;
import java.util.Optional;

import org.junit.Assert;
import org.junit.Test;

public class TestBinarySearchTree {

	@Test
	public void testBinarySearchTree() {
		Integer[] a = generateArray(10);// { 1, 23, 14, 12, 41, 11,
										// 234,
										// 52, 18 };
		print(a);
		BinarySearchTree<Integer> tree = new BinarySearchTree<>();
		for (Integer i : a) {
			BinaryNode<Integer> node = new BinaryNode<Integer>(i);
			tree.insertNode(node);
		}
		System.out.println(tree);

	}

	Integer[] toArray(BinarySearchTree<Integer> tree) {
		List<Integer> list = new ArrayList<>(tree.getSize());
		inOrderTraversing(tree.getRootNode(), list);
		System.out.println(list);
		Integer[] a = new Integer[tree.getSize()];
		return list.toArray(a);

	}

	void inOrderTraversing(BinaryNode<Integer> node, List<Integer> list) {
		if (node != null) {
			if (node.getLeft() != null) {
				inOrderTraversing(node.getLeft(), list);
			}
			list.add(node.getKey());
			if (node.getRight() != null) {
				inOrderTraversing(node.getRight(), list);
			}
		}
	}

	@Test
	public void testSortByBinartSearchSort() {
		Integer[] a = generateArray(1000000);
		long begin = System.currentTimeMillis();
		a = new BinarySearchTreeSort<Integer>().sort(a);
		System.out.println("used :" + (System.currentTimeMillis() - begin) + "ms");
		print(a, 100);
		Assert.assertTrue(isArrayMonotoneIncreasing(a));
	}

	@Test
	public void testGetNode() {
		Integer[] a = { 1, 2, 3, 4 };// generateArray(10);
		print(a);
		BinarySearchTree<Integer> tree = new BinarySearchTree<>();
		for (Integer i : a) {
			BinaryNode<Integer> node = new BinaryNode<Integer>(i);
			tree.insertNode(node);
		}
		System.out.println(tree);
		Optional.ofNullable(tree.getNodeByKey(a[a.length - 1])).ifPresent((k) -> {
			System.out.println(k);
			Assert.assertEquals(a[a.length - 1], k.getKey());
		});
		Optional.ofNullable(tree.getNodeByKey2(a[a.length - 1])).ifPresent((k) -> {
			System.out.println(k);
			Assert.assertEquals(a[a.length - 1], k.getKey());
		});
		System.out.println(tree.getDepth());
	}

	@Test
	public void testgetMin_MaxNode() {
		Integer[] a = generateArray(10);
		print(a);
		BinarySearchTree<Integer> tree = new BinarySearchTree<>();
		for (Integer i : a) {
			BinaryNode<Integer> node = new BinaryNode<Integer>(i);
			tree.insertNode(node);
		}
		System.out.println(tree);
		System.out.println(tree.getMinNode().getKey());
		System.out.println(tree.getMaxNode().getKey());
	}

	@Test
	public void testdelete() {
		Integer[] a = { 8, 2, 16, 12, 10, 20, 25 };// generateArray(10);
		print(a);
		BinarySearchTree<Integer> tree = generateBST(a);
		printTree(tree);
		// 删除根节点，被删节点有两个子节点
		tree.deleteNodeByKey(8);
		Assert.assertEquals(tree.preorderTraversing(), "10 2 16 12 20 25 ");
		printTree(tree);
		// 删除无子节点的节点
		tree = generateBST(a);
		tree.deleteNodeByKey(2);
		Assert.assertEquals(tree.preorderTraversing(), "8 16 12 10 20 25 ");
		// 删除仅有左子树的节点
		tree = generateBST(a);
		tree.deleteNodeByKey(12);
		Assert.assertEquals(tree.preorderTraversing(), "8 2 16 10 20 25 ");

		// 删除仅有右子树的节点
		tree = generateBST(a);
		tree.deleteNodeByKey(20);
		Assert.assertEquals(tree.preorderTraversing(), "8 2 16 12 10 25 ");

		// 删除有左右子树的节点，且右子树只有一个节点
		Integer[] a2 = { 8, 2, 16, 12, 10, 13 };
		tree = generateBST(a2);
		tree.deleteNodeByKey(12);
		Assert.assertEquals(tree.preorderTraversing(), "8 2 16 13 10 ");
	}

	@Test
	public void testRotateLeft() {
		Integer[] a = { 10, 1, 20 };
		BinarySearchTree<Integer> tree = generateBST(a);
		tree.rotateLeft(10);
		printTree(tree);
		Assert.assertEquals(tree.preorderTraversing(), "20 10 1 ");
	}

	@Test
	public void testRotateRight() {
		Integer[] a = { 10, 1, 20 };
		BinarySearchTree<Integer> tree = generateBST(a);
		tree.rotateRight(10);
		printTree(tree);
		Assert.assertEquals(tree.preorderTraversing(), "1 10 20 ");
	}

	@Test
	public void testprintTree() {
		Integer[] a = { 10, 1, 20, 33, 12, 5, 4, 7, 9, 34 };
		BinarySearchTree<Integer> tree = generateBST(a);
		int depth = tree.getDepth();
		System.out.println(depth);
		// 广度优先遍历
		recprint(new BinaryNode[] { tree.getRootNode() }, 0, depth);
	}

	String space5 = "     ";

	@Deprecated
	@SuppressWarnings({ "unchecked", "rawtypes" })
	void recprint(BinaryNode<Integer>[] nodes, int level, int depth) {
		if (level < depth) {
			StringBuilder s = new StringBuilder();
			// padding
			for (int i = 0; i < (Math.pow(2, depth - 1 - level) == 1 ? 0 : Math.pow(2, depth - 1 - level)); i++) {
				s.append(space5);
			}
			StringBuilder d = new StringBuilder();
			for (int i = 0; i < Math.pow(2, depth - level); i++) {
				d.append(space5);
			}
			List<BinaryNode<Integer>> tmpnodes = new ArrayList<>(nodes.length << 1);
			for (int i = 0; i < nodes.length; i++) {
				s.append(nodes[i] != null ? nodes[i].getKey() : "n").append(d);
				tmpnodes.add(nodes[i] != null ? nodes[i].getLeft() : null);
				tmpnodes.add(nodes[i] != null ? nodes[i].getRight() : null);
			}
			System.out.println(s);
			if (!tmpnodes.isEmpty()) {
				BinaryNode[] a = new BinaryNode[nodes.length << 1];
				recprint(tmpnodes.toArray(a), ++level, depth);
			}
		}
	}
}
